#include <iostream>
using namespace std;

// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点

enum Color {
	RED, BLACK
};

template<class T>
struct RBTreeNode {
	RBTreeNode(const T& data = T(), Color color = RED)
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _color(color)
	{}

	RBTreeNode<T>* _pLeft;
	RBTreeNode<T>* _pRight;
	RBTreeNode<T>* _pParent;
	T _data;
	Color _color;
};

template<class T>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Self;

	RBTreeIterator(Node* pNode)
		: _pNode(pNode)
	{}

	// 让迭代器具有类似指针的行为
	T& operator*()
	{
		return _pNode->_data;
	}
	T* operator->()
	{
		//return &_pNode->_data;
		return &(operator*());
	}

	// 然迭代器可以移动：前置/后置++  
	Self& operator++()
	{
		Increament();
		return *this;
	}
	Self operator++(int)
	{
		Self temp(*this); //先拷贝
		Increament();
		return temp;
	}

	// 然迭代器可以移动：前置/后置-- 
	Self& operator--()
	{
		DeIncreament();
		return *this;
	}

	Self operator--(int)
	{
		Self temp(*this);
		DeIncreament();
		return temp;
	}

	// 让迭代器可以比较
	bool operator!=(const Self& s)const {
		return _pNode != s._pNode;
	}
	bool operator==(const Self& s)const {
		return _pNode == s._pNode;
	}

private:
	void Increament()
	{
		if (_pNode->_pRight) 
		{ //获取右边最左节点
			_pNode = _pNode->_pRight;
			while (_pNode->_pLeft)
				_pNode = _pNode ->_pLeft;
		}

		else
		{ //当前子树访问完毕，一直查找到父节点不是子节点右子树为止
			Node* pParent = _pNode->_pParent;
			while (_pNode == pParent->_pRight)
			{
				_pNode = pParent;
				pParent = _pNode->_pParent;
			}
			
			// 注意：特殊情况-->根节点没有右孩子，迭代器在根位置
			if (_pNode->_pRight == nullptr)
				_pNode = pParent;
		}
	}

	void DeIncreament()
	{
		// 处理迭代器在end的位置
		if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED)
		{
			_pNode = _pNode->_pRight;
		}

		else if (_pNode->_pLeft) 
		{ //获取右边最左节点
			_pNode = _pNode->_pLeft;
			while (_pNode->_pLeft)
				_pNode = _pNode->_pRight;
	
		}
		else 
		{ //当前子树访问完毕，一直查找到父节点不是子节点右子树为止
			Node* pParent = pCur->_pParent;
			while (pParent->_pLeft == _pNode)
			{
				_pNode = pParent;
				pParent = _pNode->_pParent;
			}
			_pNode = pParent;
		}
	}

	Node* _pNode;
};


// T: 可能是键值对<key,value>
//    可能是一个key
// 不论节点中存储的是<key, value> || key, 都是按照key来进行比较的
// KeyOfValue: 提取data中的Key
template<class T, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T> iterator;
public:
	RBTree()
		: _size(0)
	{
		_pHead = new Node;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
	}

	// 插入值为data的节点
	// 返回值含义：iterator代表新插入节点   bool：代表释放插入成功
	pair<iterator, bool> Insert(const T& data);

	// Begin和End迭代器
	iterator Begin();
	iterator End();

	// 红黑树是否为红，是返回true，否则返回false
	bool Empty()const;
	// 返回红黑树中有效节点的个数
	size_t Size()const;
	// 将红黑树中的有效节点删除，注意：删除的是有效节点，不删除头结点
	void Clear();
	// 在红黑树中查找data，存在赶回该节点对应的迭代器，否则返回End()
	iterator Find(const T& data);

private:
	Node* _LeftMost();
	Node* _RightMost();
	void _Destroy(Node*& pRoot);
	void RotateL(Node* pParent);
	void RotateR(Node* pParent);
private:
	Node* _pHead;
	size_t _size;
};
